home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 14 / 014.d81 / solving again < prev    next >
Text File  |  2022-08-26  |  679b  |  51 lines
  1.  
  2.        SOLVING THE EQUATION
  3.  
  4.  There are techniques for solving the
  5.  
  6. linear diophantine equation
  7.  
  8. 1)       AX + BY = N
  9.  
  10. when N is divisible by (A,B), the GCD
  11.  
  12. of A and B.   Remember, if N is not
  13.  
  14. divisible by (A,B), there are no
  15.  
  16. solutions.
  17.  
  18.   Assume that (A,B) does divide N and
  19.  
  20. set
  21.                 N
  22. 2)         N'= ---
  23.  
  24.               (A,B)
  25.  
  26.   We know that there exist integers C
  27.  
  28. and D such that
  29.  
  30.  
  31. 3)          AC + BD = (A,B).
  32.  
  33. Multiplying this equation by N',
  34.  
  35. 4)      ACN' + BDN' = (A,B)N'
  36.  
  37. but by 2), (A,B)N'=N.  Thus,
  38.  
  39. 5)    A(CN')+B(DN') = N
  40.  
  41. and thus by definition,
  42.  
  43.  X=CN' and Y=DN' is a solution to the
  44.  
  45. original equation.
  46.  
  47.  
  48. --------------------------------------
  49.  
  50.  
  51.